Minimum Spanning Tree (MST) of a random generated connected Graph¶
1. Random connected undirected Graph Generation and visualization¶
In [1]:
"""
This is Matteo M.'s final Project for Stanford's Code in Place 2024.
This program find the Minimum Spanning Tree in an undirected,connected, weighted graph.
It will the visualize the path in multiple visualization tool utilizing gravis library
and jupyter notebook.
For the sake of the presentation, the graph is randomly generated utilizing Erdős–Rényi model
and enforcing the connection. The code can be easily corrected to accept a graph from user files.
"""
import gravis as gv
import networkx as nx
import random
from itertools import combinations, groupby
# Create a graph of N nodes, with a probability of P of being connected
N = 15
P = 0.2
edges = combinations(range(N), 2)
G = nx.Graph()
G.add_nodes_from(range(N))
for _, node_edges in groupby(edges, key=lambda x: x[0]):
node_edges = list(node_edges)
random_edge = random.choice(node_edges)
G.add_edge(*random_edge)
for e in node_edges:
if random.random() < P:
G.add_edge(*e)
# Generate random weight parameter for the edges
for (start, end) in G.edges:
G.edges[start, end]['weight'] = random.randint(1,100)
#Assign graph and edges
graph_input = G
graph_input.edges.data('weight')
# Centrality calculation
centrality = nx.algorithms.degree_centrality(graph_input)
# Community detection
communities = nx.algorithms.community.greedy_modularity_communities(graph_input)
# Assignment of node sizes
nx.set_node_attributes(graph_input, centrality, 'size')
for node in graph_input.nodes:
graph_input.nodes[node]['color'] = 'Red'
graph_input.nodes[node]['size'] = 10
# Plot the graph
gv.three(graph_input, use_edge_size_normalization=True, edge_size_factor = 4.0)
Out[1]:
Details for selected element
2. Minimum Spanning Tree determination with Prim's Algorithm¶
In [2]:
# Find the minimum spanning tree
mst = nx.minimum_spanning_tree(G,algorithm="prim")
# Color the edge path in green
for e in mst.edges:
mst.edges[e]['color'] = 'green'
# Plot the Minimun Spanning Tree finded
gv.three(mst, use_edge_size_normalization=True, edge_size_factor = 4.0)
Out[2]:
Details for selected element
3. Plot of the MST over the original Graph¶
In [3]:
# Add the Minimum Spanning tree path in the original graph, the mst line will show ticker and colored green
for e in mst.edges:
graph_input.edges[e]['color'] = 'green'
graph_input.edges[e]['size'] = 1.2
# Plot the graph with the minimum spanning tree
gv.three(graph_input, use_edge_size_normalization = True,edge_size_factor = 0.4)
Out[3]:
Details for selected element
4. Bi-dimensional rappresentation of the Graph¶
In [4]:
# Add a bi-dimensional model of the graph with the mst path highlighted
gv.vis(graph_input, show_node_label = True, show_edge_label = True,
edge_label_data_source = 'weight',node_label_size_factor = 1.5)
Out[4]:
Details for selected element
In [ ]: